SSH host identification changes on one wireless network

I regularly connect via SSH to a remote server, from an Ubuntu system, on the default port 22. Let's call the server example.org. I am sure that this server is configured properly, and I have confirmed that the following issue is independent from my OS and persists across re-installs.

There is one particular Wifi access point where, if I connect to the server (ssh example.org), I get this:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ED25519 key sent by the remote host is
SHA256:[REDACTED].
Please contact your system administrator.
Add correct host key in /home/user/.ssh/known_hosts to get rid of this message.
Offending ED25519 key in /home/user/.ssh/known_hosts:3
  remove with:
  ssh-keygen -f "/home/user/.ssh/known_hosts" -R "serv.org"
ED25519 host key for serv.org has changed and you have requested strict checking.
Host key verification failed.

The problematic access point belongs to an academic institution, and seems to be more locked-down than commercial ISP networks (for example I can't download torrents on it). If I go back to another network (say, using my phone as an access point), I can connect again.

According to Wireshark:

• The DNS query (to 8.8.8.8) for example.org returns the same IP address, even on the problematic access point.
• The SSH key exchange seems to happen as usual, but the key sent by the server in the "ECDH Key Exchange Reply" indeed has a different fingerprint when I am connecting through the problematic AP.

I don't understand what this network is doing. Blocking port 22 would be one thing, but here I seem to reach the server and get a wrong key as a response.

Could this access point be intentionally tampering with the SSH connection? Is there a way for me to securely use SSH over it despite this? Should I just avoid using it?

Either this systems host keys are changing or someone/something is MITM'ing the SSH connection.

The appropriate course of action is to consider that host as compromised (although its likely not the host itself, rather the connection) unless/until you have an explanation.

You may want to reach out to the system administrator of that AP and advise them of your concerns and try and track this down with them.

Since it's an academic institution, I'm thinking it's probably a firewall/security gateway that intercepts and analyzes the SSH traffic for things like Data Loss Prevention (DLP) or general audit logging.

For example of such a firewall: https://docs.paloaltonetworks.com/pan-os/9-0/pan-os-admin/decryption/decryption-concepts/ssh-proxy.html

The answer by davidgo is correct. Note that, as long as you're using pubkey auth and not password, this MITM does not compromise the safety of your credentials. But it does compromise the privacy and authenticity of anything transmitted over the session. Note that "authenticity of anything transmitted over the session" includes (rather, probably consists entirely of) commands sent to the shell or whatever process you're interacting with and output sent back.

I had originally suggested the following, which is dangerously wrong, at least without further measures:

One easy workaround is double-ssh. Assuming the host you're logging into allows port forwarding, login once with the compromised connection, using pubkey auth and with forwarding enabled to forward a local port to localhost:22, e.g. -L 12345:localhost:22. Now, you can run a second ssh session tunneled through the first, and unless the attacker is actively anticipating you doing this, this second session will have the right host fingerprint and you know that it's actually secure, not subject to interception by the MITM.

This was written hastily as a simplification from the right way I had in mind to do it, which is to have a separate login account used purely for forwarding, with no shell, which I believe is still safe to use with a compromised (MITM'd) connection, but I'd still advise caution. It may also be possible to setup your authorized_keys file to limit the key you use for the initial (MITM'd) login so that it's unable to issue any commands, only forward connections; if so, such a setup should be safe.