Compare sequence & maps headers in fasta file
Obvious things: use strict and warnings. Use three argument form of open, use lexical file handles, check the success of open or use autodie.

When I run the program, Seq6 is not reported in the output. That's because the outer loop exhausts File2, not File1.

#!/usr/bin/perl
use warnings;
use strict;

my $start_run = time;
my %hash;
my $previous;

open my $SBJ, '&lt;', 'File1.fasta' or die 'File not found';
while (&lt;$SBJ&gt;) {
    chomp;
    if (/^\w+/) {
        $hash{$previous} = $_;
    } else {
        $previous = $_;
    }
}
close $SBJ;

my %dash;
undef $previous;
open my $QUERY, '&lt;', 'File2.fasta' or die 'File not found';
while (&lt;$QUERY&gt;) {
    chomp;
    if (/^\w+/) {
        $dash{$previous} = $_;
    } else {
        $previous = $_;
    }
}
close $QUERY;

open my $OUT, '&gt;', 'Output.txt' or die $!;
my @new_array;
for my $temp (keys %hash) {
    for my $key (keys %dash) {
        if($hash{$temp} eq $dash{$key}) {
            push @new_array, $key;
        }
    }
    if (@new_array &gt; 0) {
        print {$OUT} "$temp\t@new_array\n";
    } else {
        print {$OUT} "$temp\tNot found\n";
    }
    @new_array = ();
}
close $OUT or die $!;

my $end_run = time;
my $run_time = $end_run - $start_run;
print "Job took $run_time seconds\n";


If performance is a problem, you can try trading memory for speed: Hash by the sequences, not by their names:

#!/usr/bin/perl
use warnings;
use strict;

my $start_run = time;
my %hash;

open my $SBJ, '&lt;', 'File1.fasta' or die 'File not found';
my $id;
while (&lt;$SBJ&gt;) {
    chomp;
    if (/^&gt;/) {
        $id = $_;
    } else {
        $hash{$_} = $id;
    }
}
close $SBJ;

my %dash;
undef $id;
open my $QUERY, '&lt;', 'File2.fasta' or die 'File not found';
while (&lt;$QUERY&gt;) {
    chomp;
    if (/^&gt;/) {
        $id = $_;
    } else {
        $dash{$_} = $id;
    }
}
close $QUERY;

open my $OUT, '&gt;', 'Output.txt' or die $!;
for my $seq1 (keys %hash) {
    if (exists $dash{$seq1}) {
        print {$OUT} "$hash{$seq1}\t$dash{$seq1}\n";
    } else {
        print {$OUT} "$hash{$seq1}\tNot found\n";
    }
}
close $OUT or die $!;

my $end_run = time;
my $run_time = $end_run - $start_run;
print "Job took $run_time seconds\n";


Reading the files is exactly the same code with just the hash name different. I'd refactor it into a subroutine to keep the code DRY (Don't Repeat Yourself):

sub read_fasta {
    my $filename = shift;
    my ($id, %hash);
    open my $FH, '&lt;', $filename or die "Can't open $filename: $!";
    while (&lt;$FH&gt;) {
        chomp;
        if (/^&gt;/) {
            $id = $_;
        } else {
            $hash{$_} = $id;
        }
    }
    return %hash
}


my %hash = read_fasta('File1.fasta');
my %dash = read_fasta('File2.fasta');