My Sign-Ins | Security Info | Microsoft.com
Click -> Add sign-in method
Click -> Microsoft Authenticator
Click -> Next, Next
Scan the QR
You must be able to get into your Microsoft/Email account from your old device or other method of 2FA before you can do these steps. But if you can get into it, this will allow you to refresh the current 2FA on the Authenticator app on your new device.