Hi,
In the Authenticator App, you have option to backup information and if it is enable, in the new phone you need to install Authentication App and login with the backup account to restore data. Otherwise, in the menu you have option to sign in with other options, if you select that do you see options like login with phone number or similar?