Tengo un tabla con algo mas de 50.000 registro y estos realizando la sig. consulta al menos 6 veces por segundo;

$f=mysql_query("SELECT `palabra` FROM `datos` WHERE `cat`=$data_fra[0] ORDER BY rand() LIMIT 65");

El problema que tengo es que me esta matando el server, si le saco el rand() anda perfecto, pero necesito seleccion 65 palabras al azar, con php en un array no lo puedo hacer porque el array seria muy grande y el tiempo de consumo es mayor, alguien me puede dar algun consejo?. Muchas gracias.

PD.: la tabla se actualiza pero cada 7 dias, no es una base que se actualize seguido.