Lo que podrías hacer en este caso es utilizar Cloud Messaging (FCM) de Firebase que no tiene costo. Para esto necesitas agrega firebase a tu proyecto de Android.
Para utilizar FCM de Firebase, no necesariamente debes utilizar la base de datos de Firebase, puedes utilizar tu propia base de datos privada.
Para enviar la notificación a los dispositivos móviles mediante FCM puedes utilizar el SDK de Firebase Admin que esta disponible para el lenguaje C#, mediante este SDK podrías notificar a los dispositivos móviles cuando realices un nuevo insert.
Espero te sirva.