Authenticator App Recovery Issues on New iOS Device

Question

Upgrading to a new phone has resulted in losing access to all account codes stored in the authenticator app. While it appears that a backup exists from the old phone, it was wiped before recovery could be attempted. Unfortunately, none of the personal email accounts are working when trying to initiate the recovery process.