Здесь у тебя все ОК с SQLем, но ты не там это используешь. Подсчет должен выполняться без всяких order by rand(). А тебя метод prepareQueryBeforeCount.

Правильней в initialize() указывать

$this->setDefaultProperties(array(
    'sort'    => 'RAND()',
));

Или просто в вызов передавать sort=RAND()``