Here's your problem. You need to walk faster and brisker. Your own hesitant gait leaves him confused. Walk confidently and convince yourself that he is going to stay right with you instead of questioning where he is.
Do this:
1. Go somewhere where you can take 10 very brisk steps in a straight line. No turns yet (see below). Keep your strides long and don't mince your steps. Try to do this in an open area instead of a narrow hall. Don't try to heel him more than that initially, because heeling is a lot of work for a dog. Never try to heel for longer that a couple of minutes. When you teach him to heel properly for ten to twenty steps, loose leash (more casual), walking will be a breeze. Your own pace will let him know what to do and just picking up your pace will be a cue to keep up with you.
2. Do not turn and glance at him over your shoulder. That will make him lag behind. Keep looking forward and use your peripheral vision to see where he is. His head should be just forward of your leg. If you are looking forward and walking briskly, he will pay more attention to where you are going instead of waiting for a treat to appear.
3. Do not click or treat him unless his head is just forward of your leg. If you treat him by letting your hand drop behind you, that's where he will stay, expecting a treat to appear there. Keep that hand forward of your leg. Also, do not click in his face. That can startle him into lagging. You can keep your treat hand at your waist if that helps. Just don't let him cross in front of you to get to it. Make sure you keep walking briskly as you treat. Don't hesitate or slow down. In 10 steps, he shouldn't have too much trouble keeping up and you may only need to treat him at the end of your pattern. Make a fuss when he does well. If he does do well, then you can add a few more steps, but practice just the 10 until he is near perfect.
4. Do not come to a screeching halt when you finish those 10 steps. Make the last 2 or 3 steps a bit slower. That cues him that you are going to stop and helps prevent him walking past you.
If you are planning on any obedience trials, keep him on your left side. And if you do this and can remember, always start your heeling on YOUR left foot first. That's another cue for him to heel beside you. If you are going to let him stay on your right side, start your heeling on your right foot. These subtle cues, with practice, will help him understand what you want.
Practice heeling without him a few times to get the hang of it. Really! It helps. I used to "heel" whenever I walked to the other end of the house (sans dog) or walked from the car into a building.
Walking too slow, glancing over your shoulder and dropping your hand behind you are all common beginner mistakes. So make your steps brisker, like you have a definite destination, keep your head in the direction of your movement, and keep that hand forward. Put him on leash for a while, if you worry about him lagging or wandering off.
Once he is staying with you in a straight line, then you can do turns, because turns are much harder to coordinate. When you go into a turn where you are on the inside, pick up your pace even more. You can even break into a couple of running steps. Or just walk as fast as you can for a few steps. Remember that when he is on the outside of a turn, he has to take more steps than you to keep up, so if you go really fast, that will encourage him to stay at your side. If you are on the outside, keep your pace at a normal rate because he will be forced to slow down and must compensate so he doesn't run into you.
And lastly...Don't walk like a robot. If he's having trouble keeping up try being silly. Sing. Prance. Dance. Ronnie Taft will tell you it absolutely works.
Try it and then check back in.