Under Settings > Google Authenticator > Lost your Google Authenticator.
Input your 12 Mnemonic phrase to unbind your previous google authenticator.
You can now set up a new google authenticator on your device.