Here is an extremely simplified example:
Suppose that we have a spaceship of mass 1010 kg (including cargo) at rest in space. Now, to make things simple, instead of burning a steady stream of fuel, let's suppose that we throw a 10 kg moon rock out the back at a speed of -1000 m/s. Now, the momentum of the rock is -10,000 kg*m/s, so the momentum of the ship is +10,000 kg*m/s which corresponds to a speed of 10 m/s. If you work it out, the KE has changed from 0 to 5.05 MJ, with 5 MJ in the rock and 0.05 MJ in the ship.
Now, suppose we have the same scenario, but this time the ship is already moving at 100 m/s. This time the final speed of the rock is -900 m/s and the final speed of the ship is 110 m/s. If you work it out, this time the KE started at 5.05 MJ (5 MJ ship and 0.05 MJ rock), and changed to 10.10 MJ, with 4.05 MJ in the rock and 6.05 MJ in the ship.
So, the total change in energy is the same 5.05 MJ in both cases. In the first case 5 MJ went into the KE of the rock and only 0.05 MJ went into the ship, but in the second case 4 MJ went into the rock and 1.05 MJ went into the ship.
So the efficiency increased as less energy was being thrown away in the KE of the exhaust. The actual rocket equation is more complicated because it is continuous, but that is the basic principle.