I only wanted to post this because though it is similar to @Achilleas's answer, there is an official answer from Google that is actually harder to find (cannot be linked to directly and has lower google search ranking) than this StackOverflow question:
Setting up Google Authenticator on multiple devices
You can set up Google Authenticator so that you can generate
verification codes from more than one device.
Make sure that you have Google Authenticator downloaded on all devices
that you want to use.
Go to the 2-Step Verification page.
If you've already set up Google Authenticator for your account, delete
that account from Authenticator so you can start fresh. If you have
not yet set up Google Authenticator, skip to the next step.
Follow directions as usual to set up 2-Step Verification for the
mobile app, making sure to either scan the generated QR code or enter
the generated secret key on all devices that you want to set up.
Check to make sure that all devices are working correctly by entering
the verification codes from each device and clicking Verify. Then
click Save.
Google Authenticator does not generate App Passwords. If you are
prompted by an application for a new password after turning on 2-Step
Verification, you must sign in using an App Password.
Note: If you have iOS 8.3 on your device, you will no longer have to
use App passwords to use 2-Step Verification.
It makes no constraints on types of devices and by being from google the previous claim that it is officially unsupported no longer holds. Also, the Note regarding App passwords is actually a good qualifier if you own an device that is not updated to recent iOS releases.
Best Answer
You can recover your tokens if you saved QR codes or secret keys in the process of token enrollment. Also, some services offer recovery codes which can be used to recover access to your account. Then you will be able to issue the tokens on your new phone. If you didn’t save QR codes or secret keys and don’t know recovery codes you should contact the Support team of services which you protect with Google Authenticator. They will help you to restore an access to your accounts. Then you could issue new tokens.