Это худшая задача для реляционных баз данных, что там будет происходить с foreign_key я вообще молчу, все решаемо но скорости будут не очень
Если нет связанных таблиц (что логично, твой id на самом деле не идентификатор, не вводи народ в заблуждение и назови по другому) в твоем случае скорее всего можно схитрить, можно key_id считать на лету, т.е. ключевое поле с autoincrement, но назови его по другому, например key_id_orig
1+key_id_orig-min(key_id_orig)
но это сработает только если удаление возможно только самой старой записи, если же будут удаления из середины, то порядок придется пересчитывать по другому, через сортировку всей таблицы по key_id_orig и подсчету колонок функцией row_number