Ordenar registros por campo y rand()

[Neldor]

Estoy leyendo que utilizar ORDER BY RAND() es una burrada que se debería evitar pero las soluciones que se proponen la verdad es que no se ajustan a mis necesidades, por ello os consulto por si creeis que hay alguna manera más eficiente de solucionarlo, paso a explicar el problema.

Tengo una tabla de este tipo:

Nombre Prioridad
AAA 3
BBB 3
CCC 2
DDD 2
EEE 2
FFF 2
GGG 1
...

Lo que yo quiero es sacar los primeros 5 registros ordenados por Prioridad y dentro de estos que sea de forma aleatoria, para que en este caso no siempre me devuelva CCC, DDD y EEE (aunque siempre me devolverá AAA y BBB porque tienen mayor prioridad) si no que dentro de la prioridad 2 me devuelva cualquiera.

Esto es lo que me funciona, pero quiero mejorar:

Código MySQL:

SELECT * FROM Tabla ORDER BY Prioridad, RAND() DESC LIMIT 5
 

Muchas gracias por vuestra atención