You said that you are afraid of loosing users after a leak, which implies if you don't have to, you won't tell your users about the incident.
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @ IT IS POSSIBLE THAT SOMONE IS DOING SOMETHING NASTY! Someone could be eavesdropping on you right now!
Then, yes, users will be prompted in the scariest possible language.
Compare this with HTTPS/browsers, which care not a lick if a certificate/fingerprint is different, provided that the certificate is valid and the chain is trusted.