We inject a temporary SSH host (private) key via cloud-init, and trust that temporary SSH host key just long enough to generate and retrieve the "real" (long-term) SSH host keys.
For a longer introduction and a security analysis, see https://www.joachimschipper.nl/ssh-init-vm.html.
This script is intended as stable software. But you can contact me.