I wonder if it's something like https://github.com/cea-hpc/sshproxy that sits in the middle (with decryption and everything) or if they could do this without setting up a session directly with the client.

Well, we're implicitly trusting the host when running a VM anyway (most of the time), but it's something I'd want to check before buying into the service.

EDIT: Ah, it's probably https://github.com/boldsoftware/sshpiper

will try to remember to look later.

Almost certainly it does, as public key auth takes place after setting up the session encryption