I eventually switched away from Google Authenticator to Authy because I found it incredibly frustrating that Google wouldn't let you migrate 2FA codes between devices (then, to add insult to injury, they let you migrate your Google token, and
only your Google token). Authy has worked well for me so far, having migrated phones twice since then. I've also got it on a backup tablet just to make sure I'm never completely locked out if something goes wrong.
But for the security-paranoid, I understand that letting a cloud service store your 2FA tokens is suspect, even if it's password-protected. Steve Gibson suggests the alternative: when the site generates the QR code, take a picture of it, print the picture out, keep it in your safety deposit box. When you change phones, pull the QR codes out and re-scan them.