The standard message about host key change has buttons to accept the new host key (if you are sure the change was legitimate).
Can you post the exact message you are getting? Or even better a screenshot?
My SFTP server is presenting a different key to users connecting with WinSCP GUI (Windows) clients. They get a popup window with OK Reconnect and Help.
How can I tell then to accept the new key? Apparently they are not given this option, nor can I or they find an option in configuration to allow it. I guess I'm looking for the equivalent of deleting the entry in ~/.ssh/known_hosts, so they can again connect.