I've been fighting against this chicken and egg problem in my homelab. I have a step CA SSH CA set up along with automated deployment, bootstrapping, and cert renewals with an ansible playbook. It sets StrictHostKeyChecking yes in the ssh_config for my domain so I'm happily protected against a very unlikely attacker that has a foothold in my network. Theoretically, it means I should never have to worry about host keys again.

Unfortunately, ansible does everything over.... SSH. So if I spin up a new VM or host, I have to manually trust the certificate for the first connection, which is the whole point of this article. I always have console access so I can log in and check the pub key.

There are various ways around this, including the authors suggestion with cloud init. None are very helpful for new physical hosts, though. I'm leaning towards a feature step CA supports that lets hosts authenticate themselves with an X509 cert, which you can easily get with ACME. It's so easy that you could even do it over console on a new physical host.

What I really wish is that there were something like the ACME TLS-ALPN challenge but for SSH servers. They can already present a self signed certificate, so it would just be a matter of connecting all the plumbing.