A Microsoft app for iOS and Android devices that enables authentication with two-factor verification, phone sign-in, and code generation
Hello
That's because Salesforce still wants to send the authentication request to your old phone to verify, so that you can set it up on your new phone.
If you no longer have access to your old phone, you need to reach out to your organization's Salesforce admin. They can go to Salesforce admin portal to remove your old device and trigger a new set up process for your new phone. This process cannot be done on Microsoft's side.