Map クラスは要素を挿入順で列挙するので、アクセス時に delete/set すると常に古い順に列挙されるようになります。これを利用して...

class LruMap extends Map {
    constructor(capacity) {
        super()
        if (Number.isNaN(capacity) || capacity <= 0) {
            throw new Error(`Invalid capacity: ${capacity}`)
        }
        Object.defineProperty(this, "capacity", {value: capacity})
    }

    get(key) {
        if (!this.has(key)) {
            return undefined
        }
        const value = super.get(key)

        this.delete(key)
        super.set(key, value)

        return value
    }

    set(key, value) {
        super.set(key, value)
        if (this.size > this.capacity) {
            this.deleteOldestEntry()
        }
        return this
    }

    deleteOldestEntry() {
        for (const entry of this) {
            this.delete(entry[0])
            return entry
        }
    }
}

Minify すると 400 bytes くらい。
Devtools が見やすく表示してくれるのもポイント。