Hello Sebastian,
go to https://mysignins.microsoft.com/security-info choose the Security Info tab on the left side, and there you will see your sign-in methods, and among others, Authenticator should be listed. Delete the existing one, and then add a new one. I had the same problem when I factory reset my phone.