Correct, that is totally normal. Most of the deployment steps happen away from your computer and are independent of your codebase size, so there's not a lot you can do to speed up the process.
There are various steps that are involved in deploying an app on App Engine can be categorized as follows:
Gather info from app.yaml to understand overall deployment
Collect code and use the docker image specified in app.yaml to build a docker image with your code
Provision Compute Instances, networking/firewall rules, install docker related tools on the instance, push the docker image to the instance and start it
Ensure that all deployments are successful, start health-checks and if required, transfer/balance out the load.
The only process which takes most of the time is the last part where it does all the necessary checks to make sure deployment was successful and start ingesting traffic. Depending upon your code size (uploading code to create container) and requirements for resources (provisioning custom resources), steps 2 and 3 might take a bit more time.
If you do an analysis you will find that about 70% of the time is consumed in the last step, where we have the least visibility into, yet the essential process which gives app-engine the ability to do all the heavy lifting.