Why is my primary key a separate relation taking up storage?
In PostgreSQL, the only way to guarantee uniqueness is with a unique index. So a unique index is used to implement all primary key and unique indexes in PostgreSQL.
The extra space that the primary key takes is to be expected.

Also, PostgreSQL does not maintain a certain order in the table. Whenever you update a row, it moves somewhere else, and the free space left by past updates and deletes is reused for future inserts.