Both are correct. For this expression/idiom, starting the sentence with "and" sounds normal. I don't use that expression but I have family and friends who do. In writing, I think the second sentence comes off as a little more engaging and expressive, but if spoken, you could make both sentences sound equally expressive.