You can bootstrap key exchange from a short-lived password. Not perfect but at least limits the attack time window.

Companies serious about security just have a trusted person hand out hardware with signed keys on it.

So is there a backup of the key on the hardware somewhere (in case it gets lost or destroyed)

Once you have exchanged the keys nothing stops you from creating new ones. You can for example register an additional backup Yubikey.

Small scale: You generate a keypair and give the public key to whoever is setting up your account on the server.

Large scale: You generate a keypair and give the public key to Vault or whatever, which signs it with the CA that all servers know to trust.