Пройти по массиву, складывая встреченные новые ключи в массив уникальных ключей в порядке их встречи.
Индекс ключа в этом массиве и id элемента становятся ключами для сортировки.
Отсортировать (но не взбалтывать!) и удалить добавленный сортировочный ключ.
const dict = [];
arrObj.forEach((el, i) => {
if (! dict.includes(el.key)) dict.push(el.key);
el.sorter = dict.indexOf(el.key);
});
arrObj.sort((a, b) => a.sorter < b.sorter ? -1 : (a.sorter > b.sorter ? 1 : a.id - b.id));
arrObj.forEach((el) => delete el.sorter);
console.log(arrObj);