Cantoni's answer would basically be mine. I do not share the sympathy of UUID. I think it's useful in some cases but you have to have a reason to use it and I do not think that's the case. The UUID has several problems that are not relevant here, but only the consumption of space is already one of them.
I would use BIGINT
same. I doubt you come into trouble with this. Physically, you can not have this number of rows in the table even in the next few decades. If it gets deleting too many lines I think it would make up for having a mechanism that compresses the IDs that it rotates periodically. I doubt you need to, but needing to renumber all the rows by making the proper settings where the IDs were used in other tables. Yes, of course, this is not simple and in some cases it pays off, in others it does not. Remember that if one day you have to change the type of the column, you will have similar work.
I reinforce that I doubt that it is necessary to do all this mechanism, but if you want to avoid this, I think it is better to create a combination of columns to increase the maximum number, provided that this is done in advance. You can also use a string type, which would have to do with the UUID, and control the increment by the database itself.
If you need to save even space, then use the smallest possible type, if there are too many deletions, and the deleted IDs need to be reused soon so as not to pop, I would create a free-list reusing the lines instead of removing them. Each comes that you have to remove, marks the line as removed (a proper column for this that will be used to filter) and places the ID in a table that stores a list of available IDs. When you enter, if you have an ID in this list, remove it and reuse the line by clearing it completely and saving the new data. You have to know how to do it the right way in competing environments, as is common.
No one is good, but there are some alternatives to what can be done, in addition to UUID, which is still an option.