And before you start pushing out SSL on every page you have, stop using public WiFi. They will always be insecure, no matter what you do. Tether your phone or use a VPN.
I disagree. While yes a new key would be ideal, generally while you are dealing with the existing problem you will want to reach for the old key. I am not talking about situations where you misplaced the key or the server got compromised. I am talking about a situation where your current server/VPS suddenly dies and you need to spin up a new one fast. IMO, in this case wasting time on issuing/re-issuing a cert is inappropriate. On top of this, I tend to generate the certs on my laptop (I trust its RNG and physical security more than I trust the server). The key is already here. Now I can encrypt it with GPG with the full force of my 4096 bit key that only I can decrypt and store it fairly securely this way. I believe this is good enough for personal and professional sites. In the ideal case scenario, I'd also only keep these on an encrypted flash drive for even greater physical security.
I generate and store my private keys in my secure CA environment and copy them to the server. If I ever need to redeploy them or generate a new CSR (SHA-2 anyone?), I can do it without ever logging into the server.
What kinds of threat is it that you’re concerned about?