So I've been a bit paranoid of late when reading of the actions of the NSA - and looking at the default configs of sshd that ship with distros like EL6, there is a lot that can be done - however it requires updating to a newer openssh version than the ones that ship with EL6.
I now build openssh (currently v6.7p1) in my testing repo: http://au1.mirror.crc.id.au/repo/el6-testing/x86_64/
Firstly, remove existing SSH server keys and only create the following two. Also set AUTOCREATE_SERVER_KEYS=NO in /etc/sysconfig/sshd to stop missing keys being automatically recreated on start.
rm -f ssh_host_key
echo AUTOCREATE_SERVER_KEYS=NO > /etc/sysconfig/sshd
ssh-keygen -t ed25519 -f ssh_host_ed25519_key < /dev/null
ssh-keygen -t rsa -b 16384 -f ssh_host_rsa_key < /dev/null
Then add some config to /etc/sshd/sshd_config. If you have any Match blocks, this needs to come before them. If not, add the following to /etc/sshd/sshd_config:
## Change key exchange preferences to pick secure methods.
Then eventually restart the sshd service:
service sshd restart
Remember to always keep an SSH session open to a server as you do these - as if you get it wrong, a failed start of sshd may lock you out of that system!