Sadly the software has to be in the device before it's stolen. Call the service provider to stop the account otherwise the thief could be running up a huge bll for calls and mobile data and they'll expect you to pay for it.
There are lots of utilities in the Play Store to install in your replacement.