SqlCommand Timeout Expired on Simple Insert Statement

Question

I am trying to execute a simple insert statment into a table with a large amount of rows...one of the columns in the table is of Xml data type

sqlCmd.CommandText =
   String.Format(
       @"INSERT INTO Responses (CorrelationId, LoanNumber,ClientId, Received, Source,  ResponseXml, Success, ErrorMessage)
       VALUES ('{0}', '{1}', '{2}', '{3}', '{4}', '{5}', @Xml, '{6}', '{7}')",
       correlationId, LoanNumber, ClientCode, DateTime.Now, callSource, "0", "ResponseXml contained errors.");

   sqlCmd.Parameters["@Xml"].Value = _responseXml;
   sqlCmd.ExecuteNonQuery();

However, I get hit with the Timeout Expired error.

This only seems to happen when there are a lot of rows in the table.

I don't think increasing the timeout period is a good solution considering its a very simple insert statement.

Any suggestions?

Thanks!