Assuming a work / school account.
https://mysignins.microsoft.com/security-info
- Go to Security & Privacy page > choose Additional security verification > Update my phone numbers used for account security.
- After that it will open a new window. You will see your Phone is listed and you can choose Delete.
- Choose Set up Authenticator app and it will open a pop-up box with QR code so that you can configure the app on your new device.
--please don't forget to close up the thread here by marking answer if the reply is helpful--