1 milyon kayıtlı tabloda hiç rastgele çekim yapmadım ama mantıken
id sütunu veritipi int olsa, index boyutu 4byte*1.000.000 / (1024*1024) yaklaşık 4 mb

direk SELECT * FROM tablo ORDER BY RAND() yerine

sadece rastgele id leri almayı dene

SELECT id FROM tablo USE INDEX(id) ORDER BY RAND() LIMIT 10

daha sonra IN query yapın,

daha hızlıda olabilir, daha yavaşta olabilir ama rand sıralaması kullanmayın ve kullanıcaksanızda verileri en kötüsü 5 dk da olsa cache yapın