EF can generate some monstruous SQL statements in more complex cases. That could be an issue in your case. But I also read this post where there exists a DataType mismatch which caused EF to execute way too slow.
EF expects nVarChars voor String Field / Columns, but if they are actually varchar in the Database this could lead to some serious performance issues. Hope you can sort things out with the help of the linked post.
Also, EF (or more in general I believe) "first queries" may take some time to initialize connection, initialize EF context and so forth. So you should really tackle a couple of areas where things get messed up. Does a direct repitition of the same insert statement executes a slsow as the first one?