Comment by sampullman

If you don't have the authenticator backup codes and you didn't turn on cloud sync in the app, you might be out of luck.

You can get a replacement SIM though and use it with a new phone, so the phone number recovery option should work.