Hello @Michał Laskowski ,
I am sorry that you have face this situation . Did you have backup setup to your Microsoft account on your old android phone ? Android to iOS backup and restore is not possible due to design and restrictions by the OS vendors (google & apple) . The troubleshooting section describes your scenario . Your backup is stored in the iCloud for iOS and in Microsoft's cloud storage provider for Android. On android a personal Microsoft account can be used and on iOS a iCloud account is needed.
" Changing operating systems: Your backup is stored in the iCloud for iOS and in Microsoft's cloud storage provider for Android. This means that your backup is unavailable if you switch between Android and iOS devices. If you make the switch, you must manually recreate your accounts within the Microsoft Authenticator app. "
First I will explain the android part . The linked article above shows the backup and restore procedures. The Android phone backup option looks like below.
If you have reset the old phone to default then probably the accounts data is already gone and there is no way to recover it from old phone. However if backup was enabled then the data might still be present on your Google account side.
You require to setup the same Microsoft account on your Android phone first and then try to install the Authenticator app .
Now try to use the begin restore option . You must be very cognizant about using the correct sequence. because if you select add account and add it , the old data on your online backup will be erased as the device will sync again and send any existing accounts to the google backup .
There are generally 4 ways of MFA that anyone can set . Do you remember which one you had setup ? If you had setup multiple ways of logging in , you should be able to change it using your admin Azure AD account. This will work if you have a second admin account in your test tenant . or if you had setup a second method. The screenshot you shared seem to have only MS authenticator app related options so it may not work for you . But if you have a second global admin account in your azure AD tenant . you can use that to recover this.
Another way is to setup one-time bypass for this user if you have access to the azure AD test tenant . You can use your second Global Administrator to configure One-time bypass for your account using below option:
Azure Portal > Azure Active Directory > Security > Multi-Factor Authentication > One-time bypass .
Once this is done , you will be able to login to https://aka.ms/mfasetup using your username and password and change the MFA method.
If none of the above work for you then you may need to engage Microsoft support . If you have a support plan with your dev/test account , please open a new ticket for the same. If you do not have any such plan , you can use the global support numbers to engage with support directly . Since this is a matter of account security and privacy and its impossible to verify all the details over a forum considering privacy compliance. You may have to call the global support as per your region and work with them to get this solved.
Hope this helps you resolve your issue. If the information provided is helpful , please do accept it as answer. Should you have any issue with engaging support do reply and we will help you further on this.
Thank you.