A few years ago I was travelling abroad and had my suitcase stolen - which had my laptop (with FDE) and passport inside. Fortunately I had my phone and wallet on me, otherwise I really don't know what I would have done - I probably wouldn't even have remembered the name of the hotel I was staying at that night.
Advanced Protection uses a stricter implementation than
Google has offered in the past: Only those physical
keys—along with a password—will unlock your account. If
you lose them, you can't use a printed out backup code
So, no printed backup codes for Advanced Protection users!Good point, although I think the parent comment was about Google's existing 2FA rather than the new advanced protection setting.
I guess keeping the codes with my at all times would work, but doesn't seem like that great an option (paper is easy to lose and easy to destroy). Maybe I should memorize some of them?
I am going to be switching to a USB-C one soon, though, and it only now occurred to me that I haven't really been keeping a "list" of all the sites where I've got them registered. Right now, not a lot of sites support it so it won't be too tough to find them. But I should probably be keeping a list so I at least can be sure when I've definitely replaced registered the new Yubikey in all places the old one was registered.
That doesn't really address your question as to what happens when you lose your keys, but it's perhaps relevant that there are a few warts around replacing even keys you haven't lost.
The specifics depend on the use case, but even if you fall back to something less secure like an email and TOTP, you still come out ahead overall because most authentications are done by U2F.