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.