Primära nycklar används ofta som den sekvens i vilken data faktiskt lagras. Om primärnyckeln inkrementeras läggs data helt enkelt till. Om primärnyckeln är slumpmässig, skulle det innebära att befintliga data måste flyttas för att få den nya raden i rätt sekvens. Ett grundläggande (icke-primär nyckel) index är vanligtvis mycket lättare i innehåll och kan flyttas runt snabbare med mindre omkostnader.
Jag vet att detta är sant för andra DBMS; Jag skulle våga gissa att MySQL fungerar på liknande sätt i detta avseende.
UPPDATERA
Som anges av @BillKarwin i kommentarerna nedan, skulle denna teori inte stämma för MyISAM-tabeller. Som en uppföljningsteori skulle jag hänvisa till @KevinPostlewaites svar nedan (som han sedan har raderat), att problemet är bristen på AUTO_INCREMENT på en PRIMÄRNYCKEL - som måste vara unik. Med AUTO_INCREMENT är det lättare att avgöra att värdena är unika eftersom de garanterat är inkrementella. Med slumpmässiga värden kan det ta lite tid att gå igenom indexet för att göra denna bestämning.