Obter um registro genuinamente aleatório pode ser lento. Não há muito como contornar esse fato; se você quiser que seja realmente aleatório, a consulta deve carregar todos os dados relevantes para saber quais registros ela deve escolher.

Felizmente, no entanto, existem maneiras mais rápidas de fazer isso. Eles não são propriamente aleatórios, mas se você estiver feliz em trocar um pouco de pura aleatoriedade por velocidade, então eles devem ser bons o suficiente para a maioria dos propósitos.

Com isso em mente, a maneira mais rápida de obter um registro "aleatório" é adicionar uma coluna extra ao seu banco de dados, que é preenchida com um valor aleatório. Talvez um hash MD5 salgado da chave primária? Qualquer que seja. Adicione índices apropriados nesta coluna e, em seguida, simplesmente adicione a coluna ao seu ORDER BY cláusula na consulta e você receberá seus registros de volta em uma ordem aleatória.

Para obter um único registro aleatório, basta especificar LIMIT 1 e adicione um WHERE random_field > $random_value onde valor aleatório seria um valor no intervalo do seu novo campo (digamos, um hash MD5 de um número aleatório, por exemplo).

É claro que o lado negativo aqui é que, embora seus registros estejam em uma ordem aleatória, eles ficarão presos na mesma ordem aleatória. Eu disse que estava trocando perfeição por velocidade de consulta. Você pode contornar isso atualizando-os periodicamente com novos valores, mas acho que isso pode ser um problema para você se precisar mantê-lo atualizado.

A outra desvantagem é que adicionar uma coluna extra pode ser pedir demais se você tiver restrições de armazenamento e seu banco de dados já tiver um tamanho enorme ou se você tiver um DBA estrito para superar antes de adicionar colunas. Mas, novamente, você tem que trocar alguma coisa; se você quiser a velocidade da consulta, precisará dessa coluna extra.

De qualquer forma, espero ter ajudado.