¿Cómo recalcular el índice primario?

set @pk:=0;

update 
  your_table
  set example@sqldat.com:example@sqldat.com+1
  order by pk;       <-- order by original pk

En mi opinión, tener una clave sustituta grande está bien. Probablemente es poco probable que use todo el entero máximo permitido. Considere que puede duplicarlo usando unsigned.