Making an optimal pseudo random unique code generator for voucher-like behaviour

I guess I should explain myself. Im developing a simple management system for IT tech services. This system has a website where the clients can check the current state of their order by entering their unique code. This code, of course, has to be unique, and hopefully not easy to bruteforce.

I was thinking of an output somewhere on the lines of "XKF-042", easy to read and write down. The problem arises on the generation of these values: I could use plain random data and generate both pieces of the code, but that forces me to check wether the code already exists or not, which feels like an exponential waste of resources.

A simple answer would be to just begin counting from an arbitrary number, lets say "ABC-001", and add 1, so there is no real need to check if the value already exists. The problem with that is the ease of bruteforcing; anyone could just check ABC-XXX and check the last thousand consecutive orders.

Maths are not my forte, but I know there has to be a more elegant solution to this problem. Im thinking about generating every single possible permutation for each side of the code and scramble them, so I have a list of pairs to read from thats seemingly random, and maybe shift the "right side of the code" list every 1000 codes.

Im open to any suggestions.