Pegue todos os ids, escolha um aleatório e recupere a linha completa.

Se você sabe que os ids são sequenciais sem buracos, você pode simplesmente pegar o máximo e calcular um id aleatório.

Se houver buracos aqui e ali, mas principalmente valores sequenciais, e você não se importa com uma aleatoriedade ligeiramente distorcida, pegue o valor máximo, calcule um id e selecione a primeira linha com um id igual ou superior ao que você calculou. A razão para a distorção é que os ids que seguem esses buracos terão uma chance maior de serem escolhidos do que aqueles que seguem outro id.

Se você pedir aleatoriamente, terá uma terrível varredura de mesa em suas mãos e a palavra rápido não se aplica a tal solução.

Não faça isso, nem deve pedir por um GUID, tem o mesmo problema.