Just reinstall Authy, reauthorize with your Authy account, and you're done! Helped me countless times, from when I had to rebuild my iOS install because of a backup problem to when I got a replacement device due to a hardware issue.
Unfortunately, their marketing is highly convincing. Most people (even most engineers) won't realize the tradeoff here: Authy replaces "two factor authorization" with "two password authorization". It should be clear which is more secure.
The "two factors" with GA are a knowledge factor (something you know - your password) and a possession factor (something you have - your phone number for SMS or phone for GA app).
See also https://en.wikipedia.org/wiki/Multi-factor_authentication
For gmail, Google texts me an auth code; the seed (if there is one) is in their data center. They could switch to seedless down the road since they own both sides of the auth.