Tome todas las identificaciones, elija una al azar y recupere la fila completa.
Si sabe que las identificaciones son secuenciales sin agujeros, puede tomar el máximo y calcular una identificación aleatoria.
Si hay agujeros aquí y allá, pero en su mayoría valores secuenciales, y no le importa una aleatoriedad ligeramente sesgada, tome el valor máximo, calcule una identificación y seleccione la primera fila con una identificación igual o superior a la que calculó. El motivo del sesgo es que los id que siguen a esos agujeros tendrán una mayor probabilidad de ser elegidos que los que siguen a otro id.
Si hace un pedido al azar, tendrá un escaneo de mesa terrible en sus manos, y la palabra rápido no se aplica a tal solución.
No hagas eso, ni ordenes por un GUID, tiene el mismo problema.