> The one that you might have on a bunch of servers, or give to github, or whatever
Exactly what I avoid. Each of them gets their own separate key. Never the same key to a bunch of machines (except maybe transient VMs).
But I agree, if a server changes its SSH implementation to one that does not support your existing key, it's a hassle, to say the least. In reasonable circumstances this does not happen without a plenty of warning well ahead of time, to allow you to regenerate your key in a new format.
I meant your personal identity key in ~/.ssh/id_*. The one that you might have on a bunch of servers, or give to github, or whatever. It's a good practice to periodically regenerate those, but I don't think it happens quite as often.