Здесь у тебя все ОК с SQLем, но ты не там это используешь. Подсчет должен выполняться без всяких order by rand(). А тебя метод prepareQueryBeforeCount.
Правильней в initialize() указывать
$this->setDefaultProperties(array( 'sort' => 'RAND()', ));
Или просто в вызов передавать sort=`RAND()`