Ask HN: How do you start over with 2FA after losing your phone?

I left my iPhone in a cab in Costa Rica by mistake. I may as well have thrown it into a volcano.

I have 2FA set up on three dozen different and important online accounts, and it's all through the Google Authenticator app on that iPhone.

Is there a recommended way to go about this problem?

Or have I locked myself out of my entire life?