I recently received a "PuTTY key format too new" error when trying to SSH into one of my cloud VMs.

Simply download the latest version of Putty from https://www.chiark.greenend.org.uk/~sgtatham/putty/latest.html and you should be good to go.