Deprecating RSA ssh host keys in 16

Hi all,

Last week I turned off RSA host key generation for SSH in EC2 instances,
because (a) modern SSH clients support ecdsa and ed25519 keys, and (b)
generating RSA host keys was taking over 10% of the boot time when EC2
instances booted for the first time.

I don't think we should turn off RSA host key generation in general in
15.x since for non-VM/cloud images the first boot time is less relevant
(if you're installing from an ISO image, the installer will take far
longer than the host key generation) but I think it would make sense to
deprecate RSA host keys in 15 and then turn them off by default in 16.

I'm not sure if there's any good way to announce the deprecation beyond
putting it into the release notes; we could print a warning in 15 when
RSA host keys are generated, but that will always fire regardless of
whether they're being *used* and I don't think there's any practical way
to warn specifically when RSA host keys are *used*.  So unless I'm
missing something, the deprecation would just take the form of a few lines
in the release notes.

Thoughts?

Colin Percival