Comment by joncrane

So I have used Authy, which apparently is somehow protocol compatible with Google Authenticator, and you can back up your tokens with a password. I got a new phone, installed the app, entered the password, and all my tokens were there.