In theory there is a way to do it without needing to have IdentitiesOnly yes. That is, if ssh did something like: server -> user: nonce user -> serve

In theory there is a way to do it without needing to have IdentitiesOnly yes. That is, if ssh did something like: server -> user: nonce user -> server: nonce2, h(nonce || nonce2 || publickey) (for every publickey) or alternatively user -> server: nonce server -> user: nonce2, h(nonce || nonce2 || publickey) (for every publickey) It would still leak the amount of keys (for the user for the 1st protocol and for the server for the second) but nothing about them. (I would also suggest using a modern hash function for h, such as blake(2) or sha3) There should be a way to extend this protocol as to not leak the amount of keys.