You can fix the leaked token problem if your prover also proves that (a) the private token id is not on the public revocation list, and (b) the token has not yet expired. Use short expirations and auto-renew, this is just to keep the revocation list from growing forever.

Attackers could still compromise the system with proxies, but you can fix that by (a) passing in a random sessionid from the server so proofs can't be replayed, (b) also passing in the server's public key, so a MITM attack will result in proof the server can't verify, and (c) as you mention, using secure hardware on the client, and encrypting communications between that hardware and the server. The secure hardware doesn't have to preclude general-purpose computers; it can work like a yubikey or hardware wallet, just plug into USB or bluetooth.

Without proxies, a leaked key has a minor impact unless it's widely distributed online, in which case it's easy to notice and add to the revocation list.

Tracking clients can be prevented if the client generates a new public key for each session.

Requiring hardware is in one sense a downside, and strong protections for access would have to be part of the law. But giving everyone secure cryptographic hardware that can do key management and zero-knowledge proofs would be a huge improvement for everyone's privacy and security, so it might be a good trade.