Don't operate your phone and sim card after you lost them. And find an Android sms recovery to scan your phone and see whether your deleted messages could be found or not.
If they can be scanned out, congrats, you are able to recover them back. If not, they may be covered by new generated data unfortunately.