The issue is that the server's public key has changed from the one used the last time your client connected, and it may be indicative of an attempt to fool you into connecting to a server that's masquerading as your intended target in some fashion, in order to steal your credentials or some other malicious behaviour.
The message also naturally occurs if the public key on the server has been explicitly changed, which can happen for a number of legitimate reasons - a vulnerability in Debian-based Linux distributions in the not-so-distant past necessitated key regeneration for many people, for example.
If you can confirm that you're connecting to the intended destination, and you know that any key change was legitimate, then you can usually accept the key change. Alternatively, as the message explains, you can obtain the server's public key via an alternative (secure) channel and update your client's local copy so it recognises the server's credentials once more.
If you don't control the server, contact the person or organisation that does, and find out whether the change was legitimate.
You don't need to modify your private key in any way; this is nothing to do with your key pair.