Hi Monica
Thanks for reaching out! My name is Dane and i'm an Independent Advisor and a Microsoft user like you.
You can sign in on this page
https://account.live.com/proofs/manage/addition...
Then scroll down to "Identity verification apps"
Then click on Turn off all existing apps.
Uninstall the authenticator app on your old phone
Install it on your new phone
Go back to the page where you removed it and this time choose to set up the app