As chaves primárias são frequentemente usadas como a sequência na qual os dados são realmente armazenados. Se a chave primária for incrementada, os dados são simplesmente anexados. Se a chave primária for aleatória, isso significaria que os dados existentes devem ser movidos para obter a nova linha na sequência correta. Um índice básico (não-chave primária) geralmente é muito mais leve em conteúdo e pode ser movido mais rapidamente com menos sobrecarga.

Eu sei que isso é verdade para outros SGBDs; Eu me arriscaria a adivinhar que o MySQL funciona de maneira semelhante a esse respeito.

ATUALIZAÇÃO

Conforme declarado por @BillKarwin nos comentários abaixo, essa teoria não seria verdadeira para tabelas MyISAM. Como uma teoria de acompanhamento, eu me referiria à resposta de @KevinPostlewaite abaixo (que ele já excluiu), que o problema é a falta de AUTO_INCREMENT em uma PRIMARY KEY - que deve ser exclusiva. Com AUTO_INCREMENT é mais fácil determinar se os valores são únicos, pois eles são garantidos como incrementais. Com valores aleatórios, pode levar algum tempo para realmente percorrer o índice para fazer essa determinação.