T-sql execute faster

Question

 I would like your suggestions on how to make a sql server 2008 r2 stored procedure  to run more efficiently. The stored procdure is used as a 'search' for users to see  the hitory of information before  the  user decide what  to  do  with the records they are  currently working  with. The following is the stored procedure as it exists currently:

  alter PROCEDURE [dbo].[brw_Rec]
 @rId numeric(18,0),
 @rId2 numeric(18,0) = NULL
  AS
  BEGIN
 
  select RID,PA_ID
  from app_table 
  WHERE (PA_ID= @rId) or (RID between @rId and @rId2) or
  (PA_ID= @rId) or (PA_ID between @rId and @rId2)
  END
  go

This stored procedure takes too long to execute when either of the 'between' parameters are used. The between is picking a range of values. This stored procedure can  not be split up into two stored procedures since  it is called by a C#.net 2008 desktop application.
Basically the same parameters a used  here. The PA_ID column is the parent record and the RID column is the  child record. The PA_ID column can  never have the  same value that the RID column has. This is programmed into the C#.net 2008 desktop application.
Let me know how you think this stored procedure  can be changed so it executes  faster.