Comment by Nextgrid

I was thinking the HSM in this case is your Macbook and its TPM/Secure Enclave, in which case you'd either recover it or assume the attacker is unable to use it due to biometrics/PIN. I guess the Yubikey has a PIN too with a limited number of tries.

Either way, you either recover the HSM and then don't need to rotate the keys, or you don't in which case you either use OpenSSH's key revocation mechanism (which I believe involves distributing some some sort of CRL to every server), use time-limited SSH certificates and wait out the expiry of the compromised key, or scrap the whole CA and start fresh.

Again this depends on your threat model. The somewhat uncommon requirement where you can't manage your own `authorized_keys` on the remote host complicates things a lot; if you could, then you'd use your existing access (sign yourself a new certificate using your SSH CA) to rotate the whole CA... or just keep two keys in there (primary and backup) and skip the whole CA dance, since it's purely a workaround for the hard requirement of only being able to put one key in authorized_keys.