Eating at a deficit makes trying to gain muscle a slow process. If you would like to gain muscle faster, your strategy of going surplus seems right. Keep at it, you are doing the right things and it will show eventually! Additionally, here’s some broad suggestions in case some resonate with you and others.
Diets and regimens work differently for different people. So I would preface everything by - what works for me or someone else may not work for you and you’ll need to do some trial and error to figure out what would work the best for you.
I read somewhere that you count calories to manage weight and exercise to get into/maintain shape. So that’s my TL;DR.
Weight - Weight will always be determined by calories in, calories out. Your metabolism, macronutrients intake, sleep behavior, activity level, genetics, mental health will all impact how much calories your body consumes in a typical day. When starting off, try to count the calories you are consuming as accurately as possible. Monitor your weight over a few weeks and find your average caloric consumption based on that. Then use this to determine how much calories you should be consuming to get to the desired weight within the desired period.
Carbs - Avoid too many carbs and definitely avoid high glycemic index carbs as much as possible. This is anything with simple carbs that the body breaks up easily. They are great to give you quick boosts of energy but they also fluctuate your glucose levels, and make you feel hungry sooner. This makes it hard to eat within a caloric limit and gives the unpleasant sugar highs and lows. That said, carbs are a macronutrient so don’t eliminate them completely. In fact they may help when trying to push your body harder in your workouts.
Proteins - Protein is essential for your body to create and grow muscle tissue. It’s hard to get enough protein for muscle growth just from food sources without messing up total calories so supplements help. Get 25% or more of your daily calories from high quality protein when trying to gain muscle.
Diets - Some of the recommended diets are intermittent fasting (IF), keto, paleo, vegetarian, vegan, etc. These diets have impacts beyond just your body weight but I would not get into them for this post. For your question, the most important aspect of all these diets is that they make it easier to manage your caloric intake. All these diets would also generally help you get the right macronutrients. I would suggest reading about them, finding what resonates with you and giving some a shot.
Muscle - Compound exercise weight training with exercises that work multiple muscles, like squats, deadlifts, presses, and chin ups are good for beginners. Form is more important than the weight. Some people can get into very good shape with calisthenics only. Try to avoid machines in the beginning. Weight machines work fewer muscles at a time and don’t contribute to improving balance. As you learn more about your body and the exercises, you can add and modify them to what suits you the best.
Sleep - Get good sleep and maintain your mental health. Sleep is essential for your body to work its magic of building muscle. And, if any of the above is making you miserable, it will be hard to stick with it for the long term. What even would be the point of looking great if you don’t feel good!
Personally, I’ve never been able to gain muscle and reduce weight at the same time. This means my total muscle mass is not increasing however my body is getting more in shape (which is what I’m trying to do). For some people they are able to gain muscle mass despite losing weight especially if they are just starting out with weight training. Don’t be discouraged if you fall in the first group. Once you understand your caloric intake and body, you can modify your diet and exercise to make it work for your goals.