umm, no. I have 1024 bit keys and they have continued to work fine from my Mac to various servers that have the corresponding public key. (yes they should be updated, but I have larger keys for other servers).
I use the stock ssh in /usr/bin/ssh
Perhaps you had dsa keys? Those were deprecated and support for them was dropped.