After removing the hostkeys from /etc/ssh and generating a template, cloud-init generates new hostkeys according to /var/log/cloud-init-output.log but the keys are not written to /etc/ssh/.
Because there are no hostkeys, ssh.service does not start.
I can get around this by using the noVNC shell...