A Microsoft app for iOS and Android devices that enables authentication with two-factor verification, phone sign-in, and code generation
Hello Paulo,
If you can go to your M365 account and remove the old device.
You can also try this link: https://account.activedirectory.windowsazure.com/Proofup.aspx
If you have lost all forms of access to your accounts, and the above methods also fail, you should try to contact support directly.