Mira esto lo extrai de una web:
Cita: About selecting random rows from a MySQL table:
SELECT * FROM tablename ORDER BY RAND() LIMIT 1
works for small tables, but once the tables grow larger than 300,000 records or so this will be very slow because MySQL will have to process ALL the entries from the table, order them randomly and then return the first row of the ordered result, and this sorting takes long time. Instead you can do it like this (atleast if you have an auto_increment PK):
SELECT MIN(id), MAX(id) FROM tablename;
Fetch the result into $a
$id=rand($a[0],$a[1]);
SELECT * FROM tablename WHERE id>='$id' LIMIT 1
Pone que son para 300.000 registros, pero ahi solo pone el limit en 1 y lo aumentas en 5 hace mas operaciones. De todas formas he estado mirando y hay gente con problemas ya con 150 registros.