How to restore backup from Authenticator app

Question

Hi
I use the Microsoft Authenticator and with my last switch to a new Android phone (old died) I lost my backup and with this access to all my accounts. This seems to happened when I used the login function instead "restore from backup" --> the login has overwritten the backup. Does someone has an idea to solve this? As Microsoft support is unable to even understand the problem.

Thanks a lot!