Are you running a planet-wide server farm from your 20 year old key or what? Just a few machines? If you want to regenerate your key and fixes the knownhosts files and it’s not too much hassle, then go ahead and do it. Do something else later if you want something fancier. Yes there are some hardware key encaapsulation approaches possible, some people like to use jump hosts as gateways (the remote hosts firewall block access to anything but the jump host) etc. Also people rely in part on virtual LSN security in their data centers or ISP’s.

If it’s just a few personal machines you’re probably overthinking this. I just don’t store secret keys on any remote machines, but use ssh-keygen on my laptop and ssh -A from there.