UNIX for Advanced & Expert Users

Hello experts,

I have a series issue in script that result with bad peformence and I wonder if you can assist me.

For example
I have two files:

File-New, size 15Mb.
File-Old, size 1Mb.

File-New content:
a
b
c
k
File-Old content:
d
f
a
b
c
Result fiel should be:
!a
!b
!c
-k

The current script takes every line in the File-New and search it in File-Old and add ! if found and - if not.

The script runs forever(1:30 hour...)
For 5000 lines processed against 14Mb file.

Any idea how to improve it?

The script that currently runs, do the following:
#!/bin/sh
#Input:
# $1 means File-Old
# $2 means File-New
#! - MarkForChange
#- MarkForDeletetion
while read line
do
grep -Fi "$line" $2 >/dev/null 2>&1
if [ "$?" -eq "0" ]; then
echo "! $line"
else
echo "- $line"
fi
done < $1


Do you have any idea how to improve the process.(It take more then hour to run...:-(

Thanks,
Roy.