With public key crypto you can implement a challenge response. Server generates random garbage, send to client, client signs the garbage using priv key, sends it back as a hash that the server can verify using pub key.

Another version of this is with shared secrets instead of public/private, by replacing the signature with simply HMAC(secret, garbage) and keep rest of flow same as above.