A fourth option would be just like option 3, except you only use part of the DB token in the lookup and compare the remainder in constant-time if and only if the record exists (if you're worried about the database lookup leaking a valid authentication token).

Agreed that public key crypto isn't really appropriate here.