> For hostkeys on DO you can probably get a script to run that'll request a signed certificate from a server you own.

Or just embed the signed host certificate in cloud-init.