On ubunto do sudo apt-get update sudo apt-get upgrade
Since you are using very old encryption on at least three of those boxes don't choose a keylength of 2048 or 4096 at first. First try 1024, the try with 2048 and hopefully 4096 will also work on your servers.
Are you by any chance using PuTTy's certificates? Then that may be the cause.