JonasBack in my case I still had the old phone so for each account I could go to the aka.ms/mfasetup, approve login on the old phone, add a new app, show the QR code to the app on the new phone which activates that app, and then delete the old phone. If I didn't have the old phone, I'd have to wait for the MFA Authenticator push to time out, then send code to new phone via SMS, then do the rest. Each one took about 3-4 minutes between all the approvals and changes, etc. The only thing the "backup" buys you is there is at least the unactivated stub for each account still listed on the new phone so you can just work through the list instead of having to go through add account, work/school, etc.
In my case, it was enough to make me rethink Authenticator. I know we're all supposed to use apps to avoid sim-jacking, but if I have to leave the backup SMS method enabled anyway because if I lose the phone, I can't restore from backup and login without a backup method enabled, then why even bother with the app? It's nice to not have to type in codes, but I bet I used all the time I saved redoing all the accounts for the app.