I agree with the spirit of cocojay's answer but I favor a more moderate approach.
For cardio you should increase the speed a bit, I would recommend that you measure your heart rate while you exercise and make sure it is around 150 bpm or a bit higher. Before you do that you should make sure there are no medical issues here, if you are not sure you should first check with your doctor. Then, you may find that you can only do this for ten minutes. You should then try to increase the exercise time, e.g. via interval training or simply by sticking to the ten minutes for a while until you feel that you exercise for longer. The rule of thumb is that you should not increase the time by more than 10% in one go.
As you get fitter, you will not only be able to cycle for longer, but you will also be able to cycle faster at the same heart rate. The rule of thumb for good cardio-fitness is the power to weight ratio. If you divide the amount of sustained power you can deliver (say for 20 minutes) in Watts divided by your weight in Kg, then this ratio should be 3 or higher. But then you are doing a maximum effort while in exercise sessions you should go slower. For you this amounts to about 220 Watt of power.
Another measure is the heart rate recovery rate. If you exercise for, say, 20 minutes at a heart rate of 150 bpm, then you can measure how fast your heart rate goes down if you significantly reduce the effort. It should drop by at least 30 bpm per minute in the first minute, so after one minute you should be below 120 bpm. Your resting heart rate should also get lower over time, but this is a less reliable measure for fitness.
If you do this and you keep good track of your cardio fitness, then as you gain experience with increasing your cardio fitness, you should work toward increasing this to about an hour per day. You will likely only start to lose weight when you are exercising more than half an hour per day at high intensity.
I would not recommend dieting, as that will interfere with building your fitness up to top level. It is far better to become stronger first which then will lead to an increase in your base metabolic rate to above 3000 Kcal/day. You will then gradually lose a bit of weight as your body reconfigures itself. So, you will actually start to eat a lot more and still lose a bit of weight.
I lost a bit of weight from about 62 kg to 57 kg over the course of about 6 years. I gradually increased my fitness from running 20 minutes per day 3 times per week to 50 minuted 5 times per week now. But I eat a lot more than I did 6 years ago. Had I restricted my calory intake 6 years ago, I would have lost a bit of weight, but I would not have been physically much fitter. Also, it is likely that visceral fat around the organs could have increased due to dieting.
If you tell your body that it is ok not to be superfit and that it can't always count on enough calories, then what is the logical response? Compare that to telling your body that unless it is superfit it may not survive (that's a lie but the cells in your body dont know that you are only exercising hard for fun), but that it can always count on enough calories. Obviously your body will respond differently in this case.