I’m pretty sure insert/remove do NOT take linear time, though the time is complex to compute since Lua may or may not have migrated the array to the “array part” of the table. In either case your insert/remove time will be much closer to O(1) than O(n) since the table is based on hashing. I also suspect avoiding the use of ‘nil’ as a valid value would help.
More broadly, while Lua is a great language for many things, it’s design point is not purely speed, speed, speed. If speed is really vital to you, then perhaps Lua is not the correct choice for your project?