Please let me assume that you wonder about control surface effectiveness rather than their efficiency. Both are closely related, but I prefer to address their effectiveness - doing what the pilot demands them to do.
The aerodynamic forces are proportional to the dynamic pressure $q$ of the flow, which is density times velocity squared, as in
$$q = \frac{\rho}{2}\cdot v^2$$
To create the same amount of lift at a higher altitude, the airplane has to fly faster, so in effect the forces can stay the same. Only the true air speed will be different, which helps to get where you want faster. The control surface effectivity remains unchanged.
If we dig a little deeper, the atmosphere cools down with increasing altitude until you reach the Tropopause. This cooling makes the engines more efficient but also reduces the Reynolds number of the flow around the aircraft. A lower Reynolds number translates into a thicker boundary layer, which will reduce the effectiveness of control surfaces a tiny bit and will reduce the range of their best effectivity. But this effect is so small that it has no practical consequence.
Airliners fly at transsonic speeds at altitude, so now sonic effects become more pronounced. For the control surfaces this means that they will lose their effectiveness at higher deflection angles. For small corrections all is very similar to low level, slow flight, but if you need full deflections the control surfaces are indeed less effective at altitude.
Another effect will be rather more pronounced, and this is aerodynamic damping. Damping is the tendency of a system to create additional forces from movements which run against this movement. Take a wing: If the aircraft rolls, the wingtips will move up on one side and down on the other. Both movements will add a small angle of attack, lowering the total angle of attack on the up moving tip and increasing it on the down moving tip. Both tips will see a change in lift which will counteract the rolling motion. If the rolling speed is $\omega_x$, the resulting change in angle of attack $\alpha$ at a wing station $y$ is
$$\Delta\alpha = arctan \left(\frac{\omega_x \cdot y}{v}\right)$$
As you can see, the flight speed is in the denominator, so a higher flight speed will create a smaller angle change for the same roll rate. The same holds true for the other axes of movement, and in consequence the higher-flying aircraft needs either more pilot attention or an artificial damper.
I guess it is the lower damping which made you think that the control surfaces are less effective. They aren't.