Hi @jahmal, and welcome to our community!
Dom is correct that there are plans better-suited for addressing your main concern at that amount of usage. Frequency of sending a message is certainly a good thing to consider as well (for example: maybe varying frequency of sending messages based upon speed/movement).
TLS is a common hot topic for cellular-connected IoT, and there are a few options here.
Option A: Use a Symmetric-key Cipher
A symmetric-key cipher would require you to load a pre-shared symmetric key on devices (or otherwise implement an Initial Key Exchange protocol—perhaps an initial pairing handshake over TLS upon initial boot to download/upload/exchange keys 
?).
Also, a properly-implemented and attack-resistant symmetric-key cipher would require some padding, so the encrypted payload would still be slightly larger than the plaintext, but it would only be slightly larger than the plaintext and way less in size than an entire TLS handshake-then-send-TCP-payload (and significantly way less in size than TLS handshake-then-send-HTTP-payload). This would require a custom server listening on a TCP socket, so you’d need to consider that when looking into cloud services (AWS and other cloud hosting providers do support this, even with high availability configurations utilizing load balancers!).
You never want to roll-your-own crypto if there’s a suitable off-the-shelf hardened implementation, which there undoubtedly is for AES and other symmetric-key ciphers; just note that IKE protocols are commonly attacked as well as ciphers themselves, so be cognizant of your threat model. A lot of resource-constrained devices opt for IKE followed by symmetric-key encryption, and it isn’t insane to do so when you consider how TLS works and how a badly-implemented TLS can be exceptionally weak, which takes us to Option B…
Option B: Use TLS with Session Resumption
How TLS works is it actually negotiates which ciphers and versions are mutually acceptable between the client and server, then validates the public key used for IKE via a Certificate Authority, followed by generating an ephemeral symmetric key, exchanges the ephemeral symmetric key over its IKE protocol, and then uses the ephemeral session key for encrypting/decrypting the payload data. So, TLS combines IKE (using an asymmetric-key cipher) and the use of a symmetric-key cipher for payload delivery.
In order for a TLS implementation to be secure, all of these steps must be hardened—the Certificate Authority validation, the random number generation, the IKE, and the symmetric-key cipher—and both the client and server must maintain an up-to-date list of which ciphers and versions are not known to be weak and reject any that are. So, you need a hardened TLS implementation to start with, and need a hardened update process. (You would want these for Option A too, but just pointing out for anyone reading that TLS isn’t magically secure without these other considerations being covered as well.)
The pain-point for TLS data usage is that performing the TLS handshake over and over again is costly (and especially noticeable when your payload is significantly less in size than the handshake itself). For this reason, there exist several TLS-related RFCs that define optional TLS modes that enable TLS session resumption, which reduces the number of times the handshake/IKE need to be performed. Some IoT server/client implementations that leverage TLS session resumption have extended the maximum session lengths to cover very long periods of time.
I hope this helps point you in the right direction and excited to hear how the project goes!
Best,
PFW