Earlier quoted context omitted.
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?
Ahh, now you have three problems…hrm