This is completely solved by SSH certificates. You still have the same private key in the hardware, but instead of using the public key directly, you issue temporary (~1 hour) SSH key certificates. I even automated it using an SSH proxy.
The target machines then just need to put the CA cert in the authorized_keys files.
> The target machines then just need to put the CA cert in the authorized_keys files.
The word "just" is doing a lot of work there. You update authorized_keys every hour for your entire fleet?