Hello Ahmad,
It is called Multi-Factor Authentication. First, I am not sure if you are talking about auto-fill passwords with Authenticator or the one that gives you a one-time password code. If you lose your phone or format it, it is gone. Unless you are enabled recovery in the app, you should be able to fix it if the accounts are connected to your phone number.
If you have a recovery setup, try this:
https://support.microsoft.com/en-us/account-billing/back-up-and-recover-account-credentials-in-the-authenticator-app-bb939936-7a8d-4e88-bc43-49bc1a700a40
Otherwise:
You need to go to Twitter and FB and cancel the Authenticator by getting a call or text message. You can enable Authenticator again by registering one by one afterward.
I hope it will help to solve your problem.