Generate ssh host key earlier in the boot process

[Eric Hammond]

For security reasons, the EC2 images generate a new ssh host key on the first boot of a new instance.

Please move the ssh host key generation earlier in the process so that the host key is ready by the time sshd is accepting connections.

At the moment, the ssh host key is regenerated when /etc/rc.local is run which is pretty late in the boot process, i.e., after the sshd server is already accepting connections.

This causes problems when an automated process (or a fast user) attempts to ssh to the instance after ssh is accepting connections but before the host key has been regenerated. The first connection saves the wrong (old) host key and following attempts to ssh will result in huge warnings like:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
f5:a2:74:11:55:35:e9:36:2b:ad:53:7d:67:37:cd:7e.
Please contact your system administrator.
Add correct host key in /home/USERNAME/.ssh/known_hosts to get rid of this message.
Offending key in /home/USERNAME/.ssh/known_hosts:1092
Password authentication is disabled to avoid man-in-the-middle attacks.
Keyboard-interactive authentication is disabled to avoid man-in-the-middle attacks.

[Eric Hammond (esh)]

For what it's worth, I don't consider this bug a duplicate of #370628. There are two distinct problems (ssh host keys vs. authorized_keys), though it's fine if they are fixed by the same change in the source. Not a big deal, just being pedantic.