It's two-factor authentication: something you have (phone) and something you know (password to your ssh cert). So, you have to lose both in order to lose the server.
No, both authentication factors are required, so either losing your phone or forgetting your password would be sufficient to lock you out. However, the Google authenticator PAM plugin provides emergency access codes to use in the case that the one-time password generator is not available.
I don't think this is the case. Losing either loses the server in the sense that you won't be able to access it. The fix is that the "something you have" is both your phone and emergency codes.
In security, losing the server doesn't mean losing access to the server. Losing the server means that someone else has access to the server, as in an adversary.
Yes, if you lose either factor, you can't access the server. This is why with Google Authenticator you also get a one time pad with emergency codes. However, I don't know how well this would work with two-factor SSH... you'd need a separate one time pad for each server. And I'm not sure how the Google PAM module handles emergency codes.