The voltage output is changing completely linearly, the way it is. You didn't specify what kind of LEDs you are using.
Typical indicator LEDs get pretty bright from a mA up to about full brightness at 5-10mA. After that you can run as much current as you want and you're just shortening the life. They won't get much brighter. So everything important to your eye is going to happen between around 3-5 Volt.
Before you go tearing down your circuit and trying pwm or current limiting, first you could try this:
Goal:
Make the entire range of the pot move the voltage from 2.5V to 4.5-5V, rather than 1.25V to 12V.
Halfass: change R1 to 1k or so. Add a 1k resistor in series with the 2k pot. The brightness will still not be linear and it never will be, even with a log a rith mic (I can't spell) pot (which would help). But this will increase the brightness resolution of the pot, for starters. All the really big changes happen at the knee of the resistor, where the supply voltage passes the VFD of the LED, which is probably around 3V. So you want to progressively hone in on this area. (And when you get there, you can reduce the series resistors of your LED, even).
I agree that PMW will be "more efficient" in the sense that it will be most linear to the human eye, regarding brightness. (It will not be more power efficient; but that is obviously not the goal for your circuit - I hope.) But with what you already have, you can still try this something simple.
Once you have tuned the resistor ladder optimally, you will see how well supply voltage adjustment can control LED brightness. You can probably improve, as said, with PWM. Current limiting won't be all that much better, and may be pretty similar, in fact. But you can't really compare until you use a voltage adjust circuit that is reasonably decent.
Even the PWM circuit won't be linear as far as the eye is concerned. The big changes will happen in the lower half of the duty cycle, and near full duty cycle you won't see much difference. In fact, I think the best would be PWM with a logarithmic* pot.
*wherever I say logarithmic pot, I may actually mean an anti/reverse-logarhithmic pot. For a PWM circuit like Ian posted, it doesn't matter. If you get the wrong one, just reverse the logic of the output with a transistor. Or even more simple, just power the LED from the other leg.