SQL Server - Problemas Procedimiento Almacenado

Este trabaja con un servidor vinculado al sybase. en mi ambiente de pruebas funciona ok.. y realiza la actualización correctamente obteniendo los datos desde el sybase(linked server) hacia el sql server.

El problema lo tengo en el ambiente de producción puesto que la tabla CO_HISTORICO cuenta con más de 12 millones de registros y la tabla CO_DATA cuenta con 21 mil registros. y la misma consulta que utilizo en mi store lo hago en el sql advantage del sybase es rápida, le consulté al dba y me dice que cuenta con índices... pero cuando hago en el analizador de consultas o ejecutando en store en el sql server 2008 se demora demasiado...
Empezando desde la creación del store y la ejecución. Toma demasiado tiempo.

Adjunto query

CREATE PROCEDURE [dbo].[p_seleccion]
(@is_batch_ec varchar(4),
@ladt_fecha1 datetime,
@ladt_fecha2 datetime)

as

begin
Insert Into lim_p452 ( v_cta, v_bcoref, c_moneda, c_dbcr, m_monto, d_fecdep, d_fecvalor, c_codtrn )
Select SubString ( tj.ACCOUNT, 2, 6 ) + Left ( tj.ACCOUNT, 1 ) + Right ( tj.ACCOUNT, 3 ),
tj.REFE_NUMBER,
tj.CURRC,
tj.DEBIT_CREDIT,
( Case tj.CURRC When '000' Then tj.LCY_AMOUNT Else tj.FCY_AMOUNT End ),
tj.DATE_CREAC,
tj.VALUE_DATE,
tj.TRANSACTION_CODE
From Server08.INXGEN.dbo.CO_DATA tj
Where tj.VEHIC = '001'
And tj.BRACH = '000'
And tj.BATCH = @is_batch_ec
And tj.DATE_CREAC BetWeen @ladt_fecha1 And @ladt_fecha2
And RTrim ( LTrim ( tj.ACCOUNT ) ) <> 'DELETED'
And Not Exists ( Select * From lim_p452 with (nolock)
Where v_cta = SubString ( tj.ACCOUNT, 2, 6 ) + Left ( tj.ACCOUNT, 1 ) + Right ( tj.ACCOUNT, 3 )
And v_bcoref = tj.REFERENCE_NUMBER
And c_moneda = tj.CURRC
And c_dbcr = tj.DEBIT_CREDIT
And d_fecdepic BetWeen @ladt_fecha1 And @ladt_fecha2 )
Union
Select SubString ( tj.ACCOUNT, 2, 6 ) + Left ( tj.ACCOUNT, 1 ) + Right ( tj.ACCOUNT, 3 ),
tj.REFERENCE_NUMBER,
tj.CURRC,
tj.DEBIT_CREDIT,
( Case tj.CURRC When '000' Then tj.LCY_AMOUNT Else tj.FCY_AMOUNT End ),
tj.DATE_CREAC,
tj.VALUE_DATE,
tj.TRANSACTION_CODE
From Server08.INXGEN.dbo.CO_HISTORICO tj
Where tj.VEHICULO = '001'
And tj.BRANCH = '000'
And tj.BATCH = @is_batch_ec
And tj.DATE_CREAC BetWeen @ladt_fecha1 And @ladt_fecha2
And RTrim ( LTrim ( tj.ACCOUNT ) ) <> 'DELETED'
And Not Exists ( Select * From lim_p452 with (nolock)
Where v_cta = SubString ( tj.ACCOUNT, 2, 6 ) + Left ( tj.ACCOUNT, 1 ) + Right ( tj.ACCOUNT, 3 )
And v_bcoref = tj.REFERENCE_NUMBER
And c_moneda = tj.CURRC
And c_dbcr = tj.DEBIT_CREDIT
And d_fecdep BetWeen @ladt_fecha1 And @ladt_fecha2 )

End

Gracias.