Warning – Potential security breach!

I realize this is not a new subject, but the previous post(s) I've seen on the subject didn't answer my specific problem. I'm hoping that this isn't a MitM attack, but it could be.

Error after the "Warning" is "The server's host key does not match the one WinSCP has in cache..." and I'm given the option to Update, Add, Skip, or Cancel. I did "Skip" two times and was able to get on to the server and everything looked fine, but I'm concerned that I'm passing sensitive information when I use that option.

For some more detail, my server is hosted on AWS with load balancers and an RSA key-pair. However, the error message states "The new ED25519 key details are:...". I'm no security expert, but I believe ED25519 is a completely different protocol from RSA, which makes me think there is something nefarious going on.

Any help would be appreciated.

I assume that the RSA key that you refer to is the one you authenticate with. That's different key than the host key.
See Understanding SSH Key Pairs.

If you have multiple SSH servers behind a load balancer, use Add button to cache keys of individual servers one-by-one.

Ahh, ok, good to know. I think we're all good then, thank you for the reply.

I'm getting the "Potential Security Breach" fairly often and repeatedly during the same transfer process when:

1. tens of thousands of small files are being transferred
   
2. hundreds of gigabytes of files are being transferred
   

There are no attacks, compromised systems or administrators playing around with host keys. Since PuTTY won't suppress security dialogs (see https://www.chiark.greenend.org.uk/~sgtatham/putty/faq.html#faq-hostkeys), unattended transfers are stalled until user action in the event of this warning popping up. Can WinSCP add functionality to accept the "risk" (as in "remember my choice") and continue operation?

@Guast: Does the host key prompt occur on re-key? Is your SSH server load balanced somehow? Can you post a session log file?