Una opción sería hacer zadd leaderboard highscore.(Long.MAX_VALUE - timestamp) player_id.attempt_number
(cambie Long.MAX_VALUE a lo que sea un valor razonablemente más alto posible para su marca de tiempo:un int de 64 bits firmado almacenará aproximadamente 300 millones de años en milisegundos, por lo que es posible que no sea necesario)
EDITAR:No olvides agregar ceros a la izquierda :)