1. Определите кол-во записей в таблице. Не последний ID, а именно кол-во
2. Определите рандомное значение между 0 и кол-вом-1 записей, это будет смещение
3. Получите нужную запись с таблицы:
select `id` from `localities` offset {$offset} limit 1
Не сравнивал скорость, но должно быть в разы быстрее.
Рандомное смещение можно получить как на стороне PHP, так и на стороне MySQL.
А о RAND() вам уже написали.
Детально:
У вас N записей в таблице, вам нужно получить через mt_rand(), к примеру, случайное число от 0 до N-1. Это и будет ваше смещение.
$count = 100;
$offset = mt_rand( 0, $count-1 );
