The proxy does not authenticate users. When a user shows up without a certificate, a proxy simply redirects to an OAuth2 / SAML endpoint such as Github or Google. When OAuth redirect comes back, the proxy forwards user's identity to the certificate authority (usual SSO flow), which issues an SSH certificate which gets sent back to the client.

Now, "armed" with a certificate, the client can try again, in which case the proxy simply forwards the request to the destination host, which verifies the certificate. It is the same as having a non-terminating HTTP/TLS proxy/load balancer, just for SSH.