"Unfortunately, you can’t encrypt your server key and it must be always available, or else sshd won’t start. The only thing protecting it is OS access controls."
You can encrypt the server key and only decrypt it into a loopback mount when you want to start sshd or accept a connection (I don't remember offhand if sshd reads it only once or at each connection), then unmount it. You get the same functionality as typing in your keystore password when you start apache or netscape or whatever web server (because you encrypt your https private keys too, right?). An untested poc:
# making the image
mkdir TMPFS
mount -t tmpfs -o size=4m tmpfs TMPFS
cd TMPFS
dd if=/dev/zero of=servkeys.img bs=1m count=2
mkfs.ext2 -F -m 0 -t ext2 servkeys.img
mkdir MOUNT
mount -t ext2 -o loop servkeys.img MOUNT
cp /etc/ssh/sshd_config MOUNT/
ssh-keygen -t rsa -b 4096 -f MOUNT/ssh_host_key
umount MOUNT
gpg -se servkeys.img
mv servkeys.img.gpg ..
cd ..
umount TMPFS
# running sshd
mount -t tmpfs -o size=4m tmpfs TMPFS
cd TMPFS
gpg -d ../servkeys.img.gpg > servkeys.img
mkdir MOUNT
mount -t ext2 -o loop servkeys.img MOUNT
sshd -f MOUNT/sshd_config -h MOUNT/ssh_host_key
umount MOUNT
cd ..
umount TMPFS
Out of band. A vSphere console, VPN, KVM, LOM, modem... As a super-cheap alternative, a bastion host vps can be the intermediary. After connecting to the bastion host, you can then connect over the cloud provider's private network to a stripped-down remote shell on the target, and enter the password to bring up the public remote shell. Keeps the real keys safe, adds a layer in front of the target, and is convenient enough to administer from a mobile device.
How is it any more moot than the private key loaded into RAM by your https server? It's still not on disk, and it's still more difficult to extract from memory than from the disk.
You can encrypt the server key and only decrypt it into a loopback mount when you want to start sshd or accept a connection (I don't remember offhand if sshd reads it only once or at each connection), then unmount it. You get the same functionality as typing in your keystore password when you start apache or netscape or whatever web server (because you encrypt your https private keys too, right?). An untested poc: