Zend certified PHP/Magento developer

Moving authenticator app accounts to new phone (or another app)

I had all my accounts setup on my Microsoft Authenticator app on my Android phone. Now I got a new Pixel phone and want to move all those added accounts to the new Microsoft Authenticator app so I can get rid of my old phone!
I have been able to move the accounts to my new phone but the codes generated are different and none of the systems accept it. How can I fix this?

To make it worse, two of the accounts setup are government accounts and I CANNOT change the authenticator app connected to my account unless I delete it (WTH!). Any ideas?

PS: Not sure where I should post this! Let me know if there’s a better place for this