Google Play Services have an ability to use modular dependencies to reduce resulting .apk size drastically since version 6.5. Google Cloud Messaging is provided as a such module probably since version 7. The current version is 7.5.
Please use the GCM modular dependency with the AeroGear Push module, it will reduce package size and compile time.
The required dependency declaration is presented here.