Come ricalcolare l'indice primario?

set @pk:=0;

update 
  your_table
  set [email protected]:[email protected]+1
  order by pk;       <-- order by original pk

A mio parere, avere una grande chiave surrogata va bene. Probabilmente è improbabile che utilizzi tutto il numero intero massimo consentito. Considera che puoi raddoppiarlo usando unsigned.