Las claves primarias se utilizan a menudo como la secuencia en la que se almacenan realmente los datos. Si se incrementa la clave principal, los datos simplemente se agregan. Si la clave principal es aleatoria, eso significaría que los datos existentes deben moverse para colocar la nueva fila en la secuencia adecuada. Un índice básico (sin clave principal) suele tener un contenido mucho más ligero y se puede mover más rápido con menos gastos generales.
Sé que esto es cierto para otros DBMS; Me atrevería a suponer que MySQL funciona de manera similar a este respecto.
ACTUALIZAR
Como indicó @BillKarwin en los comentarios a continuación, esta teoría no sería válida para las tablas MyISAM. Como teoría de seguimiento, me referiría a la respuesta de @KevinPostlewaite a continuación (que ya eliminó), que el problema es la falta de AUTO_INCREMENTO en una CLAVE PRINCIPAL, que debe ser única. Con AUTO_INCREMENT es más fácil determinar que los valores son únicos ya que se garantiza que serán incrementales. Con valores aleatorios, puede tomar algún tiempo recorrer el índice para tomar esta determinación.
