Generally it is not expected for a deployment to take 25 minutes. I'll explain one possible cause below.
App Engine deployments interact with the bucket staging.<project-id>.appspot.com. This bucket is created by default the first time you deploy to App Engine and is used to store intermediate build outputs in order to lower the time of forthcoming deployments in a similar fashion as Docker layers. Most of the time this helps to increase the deployment speed by not requiring to "re-build" the parts that hasn't changed.
The files stored in the staging bucket are wiped out after 15 days of their insertion. However, in cases where an application is deployed a large number of times with file changes in a short period of time, a lot of temporary objects are created in the bucket and the size of it grows. This may slow down the deployment since all of them will be scanned to search for reusable intermediate builds.
If that sounds like your use case there is a workaround that consists in using the gcloud flag --bucket which allows to use a user provided bucket instead of the staging one.
gcloud app deploy --bucket <YOUR-BUCKET>
Nonetheless, if this doesn't solve the problem you would probably need to open a support ticket so that the issue could be investigated further given that here we lack the tools to do it ourselves.