One aspect of this is new RSA and ECDSA keys for SSHv2. The existing DSA key used within SSHv2 has been retired. (Note, there were no previous RSA or ECDSA keys for SSHv2, so these keys do not replace old keys). Your SSH client will likely complain about seeing a new key.
We have also implemented a host of new protocol restrictions. These include
The rationale for these changes is more-or-less consistent with current reasonable practice for cryptography. We generally sought to use primitives that could provide at least 112 bits of symmetric security, removed primitives that posed problems within the SSHv2 protocol, and disabled primitives that haven't undergone much cryptographic scrutiny.
We generally want the (ephemeral) Diffie-Hellman (or its elliptic curve based analogs) to produce keys that are of strength sufficient to make passive bulk surveillance unrewarding. Actively compromising the long term secrets on this machine may result in a situation where an active attacker may be successful, but previous sessions should not be compromised.
SSHv1 is a very old cryptographic protocol that was not designed by a cryptographer, and has some fundamental protocol-level flaws that can't be fixed. As such, this protocol version was disabled.
DSA is mostly a fine algorithm (so long as those signing messages have access to a reasonable source of random numbers), but OpenSSH only supports a modulus size of 1024 bits (roughly corresponding to 80 bits of symmetric security), and this was below the security level desired. (Please note that the OpenSSH group's complaints that FIPS 186-2 only supports 1024 bits are true, but irrelevant; newer versions of this standard have supported reasonable key lengths since 2009).
The host's RSA key is 2048 bits, which provides roughly 112 bits of symmetric security. The host's ECDSA key uses nistp256, and provides roughly 128 bits of symmetric security.
We do not, at present, support ed22519, which is particular parameter selection for the EdDSA signature scheme. EdDSA is a variant of Schnorr signatures, which are themselves variants of ElGamal; DSA and ECDSA share the same lineage. The EdDSA signature system is presently fairly new (it was introduced in 2011), and not presently well analyzed.
Rogaway pointed out that, with CBC mode, using an IV that an attacker can predict undermines the security of the underlying algorithm. SSHv2 suffers from this malady, so algorithms using CBC mode with SSHv2 have been disabled.
Arcfour (RC4) has been known to be insecure for more than 20 years, and continued use in almost any application is at best brittle, and at worst foolhardy. All Arcfour (RC4) ciphers have been disabled.
This leaves us with a few stream-cipher-like modes of AES: counter mode, and Galois Counter Mode, all of which provide a reasonable level of security when used correctly (e.g., when the counter does not repeat under the same key. Support for the CTR modes in SSHv2 is reasonably "new" (they are specified in a RFC published in 2006), but these modes are well supported across most modern clients. In OpenSSH, support for the GCM modes is proprietary (that is, not specified in a SSHv2 standard) ciphers aes128-gcm@openssh.com and aes256-gcm@openssh.com, and requires building a recent version of OpenSSH (newer than v6.2) against a recent version of OpenSSH (newer than v1.01). We use an older version of OpenSSH, so we can't support these GCM modes.
The proprietary cipher choice (that is, not specified in a SSHv2 standard) "chacha20-poly1305@openssh.com" makes use of chacha20, a stream cipher that is not well studied at present, and is coupled with the poly1305 MAC (with key expanded using chacha20!), which is similarly quite new and not well studied. Finally, this code triggered a compiler bug, and had to be excluded to get the current ssh code base to compile.
The HMAC construction is well analyzed and reasonably quick, so we restrict the available MACs to HMAC based primitives. Truncation provides only marginal operational advantages and reduces security, so we disable all truncated HMACs.
MD5 has been known to be insecure for about 20 years; there hasn't been any significant problem found with MD5 within HMAC primitives, but it doesn't provide any advantage, over other (quite secure) SHA-* HMACs, so all MD5-based MACs have been disabled.
SHA-1based HMACs do not provide the desired 112 bits of symmetric security, so we'd ideally be able to remove support for them. Sadly, support for the various SHA-2 modes is new enough that this setting breaks many reasonably up-to-date clients. Additionally, SHA-1 is baked in to the protocol level (all non-ECDSA signatures use SHA-1 has the underlying hash), so even if we prevent SHA1-HMAC from being used, SHA-1 is still used within the protocol.
RIPEMD-160 has not been as well studied as the SHA family, so it has been disabled.
MAC-and-encrypt is now regarded as generally bad practice (it turns out the question of how to couple encryption and MACs is a subtle question), so the proprietary modes (that is, not specified in a SSHv2 standard) encrypt-then-MAC ("etm") modes are supported.
For key exchange algorithms, the tragically named "group 1" (which is actually Oakley Group 2!) only uses a 1024 bit modulus, so does not fulfill the 112 bit symmetric equivalent strength requirement. Group 14 (which is Oakley Group 14) uses a 2048 bit modulus, so this is sufficient. SHA-1 (when used as a PRF) has sufficient strength to accommodate security strengths up to 160 bits, so we don't exclude the SHA-1 based key exchanges.
The concern regarding the NIST elliptic curves is rather nebulous. The selection of parameters for the NIST curves was indeed somewhat mysterious, but it seems unlikely that the NSA would deliberately inject globally attackable systemic weaknesses (that could be taken advantage of by anyone once the appropriate attack is publicly known) into curves that they recommend be used to protect of top-secret information. This is a very different situation than injection of back doors that require knowledge of specific information, as was apparently the case with the Dual_EC_DRBG.
The approach used to generate the NIST Elliptic Curves is verifiable, and though there are indeed many "bits of control", it seems unlikely that anyone could have (without reversing SHA-1) anything resembling such a back door parameter. Indeed, though there are many ways that an entire curve could be attackable, we don't know of any way to make a curve attackable only to someone who knows a particular back door secret. (That is, it's easy to make curves that can be attacked by anyone with the appropriate attack, but we don't know how to make curves that are attackable only by someone who knows a particular secret).
The NIST curves are known to not be complete, which likely leads to side channel attacks, but OpenSSH makes no attempt at resistance to this style of attack generally.
Having said all that, we do support the proprietary key exchange method (that is, not specified in a SSHv2 standard) "curve25519-sha256@libssh.org", which is Elliptic Curve Diffie-Hellman, but over Curve 25519. This curve has been transparently generated, and has a series of other nice security properties.
Most modern SSH client support algorithms that will connect; if you can't currently connect, make sure you are using a recent SSH client, and make sure that support for modern algorithms is enabled.