The database doesn't really care about 'holes' in auto_increment columns, and it doesn't result in any loss of performance ... but you have two choices:
ALTER TABLE table_name
DROP auto_incremented_column,
ADD auto_incremented_column MEDIUMINT UNSIGNED AUTO_INCREMENT NOT NULL,
AUTO_INCREMENT = 1;
The other option is run the same query without the AUTO_INCREMENT parts:
ALTER TABLE table_name
DROP auto_incremented_column,
ADD column_name MEDIUMINT UNSIGNED NOT NULL;
and then use LAST_INSERT_ID(column_name+1) in your INSERT statements
The first way is much easier, because it will automatically reassign values to the the column, whereas you'll have to do it manually, with the second way.
