All this can be done in an ssh session, however if anything goes wrong, you’ll need console access to fix the problem.

Generate new candidate primes

ssh-keygen -G moduli-2048.candidates -b 2048

Screen primes for suitability

ssh-keygen -T moduli-2048 -f moduli-2048.candidates

Install in ssh config root, backup old moduli:

cd /etc/ssh

mv moduli moduli.bak

mv moduli-2048 moduli

backup existing private/public keys:

for i in *_key;do mv $i $i.bak;done

for i in *.pub;do mv $i $i.bak;done

Generate new keys:

ssh-keygen -A

Restart sshd:

/etc/init.d/sshd restart

Verify this by logging out and back in. Your ssh client should bark that the host key has changed. Once you clear the line from .ssh/known_hosts (or the equivalent) you should be able to log in again.

At that point you should delete the old keys and candidate moduli