You actually have all the information you need. CR123A is what you need to buy. They happen to be 3V, and up to 1500mAh, lithium chemistry but not rechargeable.
You should be able to find them in a camera shop, a chemist, or even a large supermarket, but it's readyeasy and cheap to order them online.
There is a rechargeable in the same shape, with a slightly higher voltage that might still work, but getting a charger for it isn't easy, so the batteries are rare as well. In an analogue camera they last ages (many, many rolls of film when I used to use a compact that took them).