Ордер бай ранд всегда является нагрузкой на любую РБД, самый эффективный метод - перенести часть логики из бд в приложение.
Делается селект макс ид, затем в диапазоне 1-макс. программный рандом индексов, с оверхедом раза в 3-4, и делается запрос ин уже с готовыми рандомными айдишниками и ордеор бай ранд, лимит сколько надо.
Из нюансов каждая запись имеет вес, т.е. некий процент успеха выбора.
В вашем случае берется оверхед побольше, и ордер бай вес, таким образом более тяжелые веса у вас вероятнее попадут в выборку.