Either create the ssh host key outside and set it inside the image or integrate the new host into your configuration management and report the sshd host key bac

Either create the ssh host key outside and set it inside the image or integrate the new host into your configuration management and report the sshd host key back and export it to the zone database. Of course your AMI could also just automatically populate the DNS entry via some shared secret or API ...