SELECT *
FROM `choises`
WHERE questionid = :qid
ORDER BY correct DESC, RAND()
LIMIT 5
Asumiendo correct es una especie de int. De lo contrario, es posible que deba cambiar DESC a ASC .
Puede 'mezclar' los 5 resultados usando uno más ORDER BY RAND() así:
SELECT * FROM (
SELECT *
FROM `choises`
WHERE questionid = :qid
ORDER BY correct DESC, RAND()
LIMIT 5
) as t
ORDER BY RAND()