How do I create a valid SPF record? (google apps mail)

I changed the MX records for my domain to work with gmail, but they are working slow (4-8 hours delay on recieving mail).
So I went to google apps toolbox, typed down my domain to see a diagnose and the only error is:

There SHOULD be a valid SPF record.

Do you know what this is and if this is the real problem here?
If so, how to I create one?

Thank you!

I’m not using gmail, and haven’t had to do this, but here is the documentation:

and microsoft has a tool to generate the value in correct format: (and I have used that for a customer)

Via TXT record: