Follow the instruction on this https://support.microsoft.com/en-us/account-billing/change-your-two-step-verification-method-and-settings-c801d5ad-e0fc-4711-94d5-33ad5d4630f7
Basically go to office.com/apps click on your profile, select View Account, then go to Security Info and Add sign-in method, then just follow instruction. I did the same thing and now Authenticator App work on my new phone.
Also remember to delete your old phone in the sign-in method list.