I think your problem is that you are not commuting daily. Clearly this is not possible if you have to be out and about off site, meeting clients and attending other events, however, you should aim to commute by bike every day, come rain or shine. Ice and snow should not really put you off and even not riding in fog because it is 'dangerous' is a little bit light-weight! You have got to be doing it every day to get to and maintain the speed you need to do it every day. Take a few days out and what once seemed heroically-manageable suddenly seems like hard work.
Putting in a good time regardless of what goes on en-route should be highlight of the day, twice over. It should not need to feel like it is a chore. Fitness is not the be-all and end-all of setting a good time, you need to think that every second counts and ride that way. That begins from the off, some people can just leap on a bike and go, others take a mystery ten seconds just mounting the bike for some reason.
Become a meticulous time keeper. Be at your desk with coffee and logins already done by 9, don't be one of those cyclist that materializes some time after nine and spends until 10 showering, putting together a 'I am more athletic than you' breakfast and so on. Arrive on time and you can 'fairly' leave on time, taking any 'must do' work home with you. By leaving at the same time you can 'race yourself home' rather than trudge home to have half your evening already gone.
Use check-points. When cycling in it can be easy to go into a 'world of your own' and not really be focused on setting a good time. If there are any clocks along the way on public buildings expect to see certain times on them and, if you are running late on one checkpoint, put in a bit of an effort to make it to the next checkpoint on time. Obviously you can use a watch or speedometer for timing your checkpoints, but I personally like seeking out clocks, no matter how distant they are and using them for my en-route time keeping.
Every second counts, and that is all the way. Really your route through town is all about clearing obstacles that are different in same-but-different ways every day. Be observant of other riders and what they do to be quicker than you in situations. Jumping lights may not be your thing, however, making a good getaway just as the lights change really does save all important seconds. Learn the light cycles on your route and pre-empt each of them, to lay down the speed or not depending on what you can tell from having a good look ahead. This stuff really falls under the category of being the tortoise instead of the hare. Don't miss easy-win opportunities to get ahead.
Ride assertively, but not aggressively. Conflabs with motorists do not help your time. They are not a-holes, they are fellow road users that you form an on-road community with. Take up as much road as you need and use the lanes they use to make turns etc. Politely wave to them if they hoot at you because they think the outer lane is for them and not cyclists making a turn.
Take aero seriously. That billowing coat might be nice to have on but it is taking scores of seconds out of your time. If it is cold when you first leave the door just shove a plastic bag down your jersey to keep the breeze off your chest. You can pull it out five minutes in to your ride when you can handle the chill. Bags are another aero consideration. Check out the recently posted 'seat bag' question for some tips on that.
Be careful about your bike. Tyres pumped 'hard enough' are not the same as tyres pumped with a track pump. Have the brakes and gears working properly so you can get away without any un-wanted clunks and stop a bit better than a panamax supertanker. Keep the bike as well serviced as a soldier maintains his gun and it will save you those seconds. That carbon-fibre wannabee bike won't help, work with what you have got, keep it maintained and correctly adjusted for you. The only go-faster accessory that really will help are pedals, of the clipless variety, with shoes to go with. MTB SPD are what you want for the commute, not 'roadie' ones.
Those are the 'basics' of setting a good time on the commute, now onto your actual question. Your extra exercises to improve stamina and strength.
Because a bike has gears there really is not a lot of strength needed. Cycling is an aerobic exercise and higher cadence matters more than out and out strength for the ride you are doing. Remember that muscle weighs and any extra muscle has to be dragged along for when it might be needed, which will not be most of the time. That said, strength matters when pulling away from the lights or pushing up a hill. But that level of strength will come to you if you put in the miles. The same can be said for stamina. Yes you can get a trainer rig setup in the living room for your bike, or go to the gym or go for a swim, however, you are putting in a quality distance in on the bike and there should be no need for any extra-curricular extras. Just ride every day if you can and it will come to you.
Diet.
Hopefully you have a lovely partner and you don't have to lift anything more than a fork at din-dins time. At lunch and snack times you may think 'well, I am burning off x thousand calories a week, I can eat what I like'. You may also eat 'healthy' pre-prepared sandwiches from the supermarket near to your work or indulge in a sausage roll from the local bakery or pick up a small cake selection mid-ride. It is all too easy to go for quantity rather than quality. But, for maximum vitality you do need to look at everything you eat and see if you can do much, much better.
This need not be a miserable process such as what dieters put themselves through. You can up your vegetable and fruit intake, try new recipes and revitalise your passion for food to eat better stuff that is a pleasure to indulge in. Get your main meal right and you won't need to see a chocolate bar, packet of crisps, bottle of pop or other junk-food-ready-eat ever again.
One top tip for yourself and any other male reader wanting ideas is to get a bread making machine. You tip the ingredients in, set the timer and get a lovely loaf out, no washing up involved. In one stroke you are getting better bread than anything you can buy in the shops and you can start taking in your own sandwiches packed to the gills with goodness. The flour in your bread can be the good stuff that does not need all of the E numbers to keep it presentable. You can also add some mixed fruit, a couple of eggs and a spoonful of honey to your basic bread mix to make yourself the yummiest ever luxury-ready-eat item, knowing that nothing in it is anything but 100% good for you.
A lot of top athletes have gone 100% vegetarian, the world's best sprinter Mark Cavendish is probably the prime example, so consider following his example to get your cycling form to what it should be.
It does not take any money to become a cycling foodie, just an interest in doing better with your own chopping board, vegetable steamer, oven and bread machine than anything you can get ready made. Even that evil pizza can be a gourmet-healthy meal item with a DiY bread machine attitude. And no, it does not take longer to do food properly and even if it does the enjoyment is so worth it. You will make up a lot more time than time spent cooking by having better energy levels.
It took me a long time to find out how important the cycling food thing is, I lived many years under the illusion that it was calories that mattered, but, for me, it was actually only when I bucked up my ideas about cooking and food that I discovered how wrong I was. To then take over in the kitchen and try new recipes took some confidence, but you do need to be in control of what you eat if you are taking your diet and shape seriously.
To summarise, you have a splendid route that could be abbreviated with some on-bike time management improvements. You need to be going every day even if that kills you. It will come to you effortlessly after a sustained month of doing it every working day. Then there is the matter of diet, garbage in, garbage out. Up your eating game and you will notice benefits on the bike. I am sure a lot of the above is what you know already from doing running, but, you are on the right track and it will come to you.
