I use cloud-init to set up authorized_keys when the VM is created. Among them is an entry generated for this specific deployment.
After I connect to what should be my VM over SSH, I send it an encrypted one-time-use token that it can use to have the CA sign it's SSH host key.
It's symmetrically encrypted using that SSH pubkey as the password. So if it's my VM, it can be decrypted. If it's an attackers VM, it can't.
Once the host key is signed, I remove that extra SSH key since it's no longer needed.
I had someone else look it over and they didn't find any flaws in the design (or implementation for that matter). It's a little awkward, but highly effective, and it uses only technology that exists now.
This also works for deploying the CA server itself, even on the initial. Anything that needs to be secret gets encrypted with that public key. If I can decrypt the public CA certificate, then it must have been generated by my server and not an imposter.
If I am restoring the CA from a backup, only the legitimate server can decrypt the CA private key. So the same trick works everywhere.