From what I remember when I used Authy briefly (Google Authenticator finally added the ability to mass import/export codes shortly after I ended up trying Authy), you create a login and set a master password, and then you have access to your codes on any device when you log into the app. Of course, this means that you have to trust Authy with your codes being stored externally, but this might be one of the sets of circumstances where that's preferable.
I did some more research. It looks like there is a way to recover if you don't have the phone number or the old device. They have an online form you fill out with your old phone number and new phone number. Then they have some process to verify ownership of the phone numbers which they say will take several days for security purposes.
Authy doesn't store your codes. They store encrypted copies. They are encrypted on your device and only decrypted with your password which does not leave your device. As long as their encryption is not broken your codes are secure.
